package srcInterviewPrep;

public final class Fibonacci
{
    public static int GetFibNum(int n)
    {
        if (n == 1)
        {
            return 0;
        }
        
        int fib0 = 0;
        int fib1 = 1;
        int fib;
        
        for (int i = 2; i < n; ++i)
        {
            fib = fib0 + fib1;
            fib0 = fib1;
            fib1 = fib;
        }
        
        return fib1;
    }
    
    public static int GetFibNumRecursive(int n)
    {
        if (n == 1)
        {
            return 0;
        }
        
        if (n == 2)
        {
            return 1;
        }
        
        return GetFibNumTailRecursive(n-2, 0, 1);
    }
    
    private static int GetFibNumTailRecursive(int n, int fib0, int fib1)
    {
        if (n == 0)
        {
            return fib1;
        }
        
        return GetFibNumTailRecursive(n-1, fib1, fib0 + fib1);
    }
}
